//一 O(1) 常数阶
function constant(n:number) {
  for (let index = 0; index < 3; index++) {
    console.log('O(1)')
    
  }
}
//二 O(log n)对数阶
function logar(n:number) {
  let count = 0
  while(n>1) {
    n = n/2
    count++
  }
}

//三 O(n)线性阶
function linear(n:number) {
  for (let index = 0; index < n; index++) {
    console.log('O(n)')
  }
}
//四 O(n^2)平方阶
function quadratic(n:number) {
  for (let index = 0; index < n; index++) {
    for (let index2 = 0; index2 < index; index2++) {
      console.log('O(n^2)') 
    }
    
  }
}
//五 O(2^n阶)指数阶:每一个细胞的分裂都算一次
function expinential(n:number) {
  let now = 1//当前细胞个数`
  let count = 0//细胞分裂总次数(依赖now)
  for (let index = 0; index < n; index++) {//分裂N次
    for (let index2 = 0; index2 < now; index2++) {//当前细胞总数now，所以需要操作now次
      count++
    }
    now = now*2//此次分裂完，细胞的个数
  }
}
//递归场景
//1.0 细胞分裂:整体分裂N次之后，返回值n次之后，细胞分裂的总次数.  
/**
 * 原理如下:
 * 
 * 总次数是2^n - 1
 * 第n次是 2^n-1 = 2x2^(n-1)-1
 * 第n-1次是2^(n-1) - 1
 * 第n次和第n-1次的关系很明显了,设第n-1 次是count，那么第n次= 2xcount + 1
 *  */ 
function expRecur(n:number):number {//n 代表现在细胞总数
  //终止条件
  if(n === 1) return 1;
  return expRecur(n-1) +  expRecur(n-1)
}

//2.0斐波那契数列:返回值是第n个数是几
function febernq(n:number):number {
  if(n<1) return 0
  if(n===1) return 1
  if(n===2) return 1
  return febernq(n-1) + febernq(n-2)
}

console.log(febernq(8)) 
